package features.advance.leetcode.math.easy;

import java.util.Stack;

/**
 *  剑指 Offer 30. 包含min函数的栈
 *
 *  难度：简单
 *
 * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
 *
 * 示例:
 *
 * MinStack minStack = new MinStack();
 * minStack.push(-2);
 * minStack.push(0);
 * minStack.push(-3);
 * minStack.min();   --> 返回 -3.
 * minStack.pop();
 * minStack.top();      --> 返回 0.
 * minStack.min();   --> 返回 -2.
 *
 * 提示：
 *
 * 各函数的调用总次数不超过 20000 次
 *
 * 注意：本题与主站 155 题相同：https://leetcode-cn.com/problems/min-stack/
 *
 * @author LIN
 * @date 2021-06-08
 */
public class Offer30 {

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.min();
     */
    public static void main(String[] args) {
        MinStack minStack = new MinStack(){
            Stack<Integer> A = new Stack<>();
            Stack<Integer> B = new Stack<>();

            @Override
            public void push(int x) {
                A.add(x);
                if(B.empty() || B.peek() >= x)
                    B.add(x);
            }
            @Override
            public void pop() {
                if(A.pop().equals(B.peek()))
                    B.pop();
            }
            @Override
            public int top() {
                return A.peek();
            }
            @Override
            public int min() {
                return B.peek();
            }
        };
        minStack = new MinStack(){

                int[] top = new int[20000];
                int[] min = new int[20000];
                int size = 0;
                int minIndex = 0;
                /** initialize your data structure here. */
                @Override
                public void push(int x) {
                    if(minIndex == 0 || x <= min[minIndex - 1]){
                        min[minIndex++] = x;
                    }
                    top[size++] = x;
                }
                @Override
                public void pop() {
                    if(top[size - 1] == min[minIndex - 1]){
                        minIndex--;
                    }
                    size--;
                }
                @Override
                public int top() {
                    return top[size - 1];
                }
                @Override
                public int min() {
                    return min[minIndex - 1];
                }
        };
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.min());   // --> 返回 -3.
        minStack.pop();
        System.out.println(minStack.top());    //  --> 返回 0.
        System.out.println(minStack.min());   //--> 返回 -2.

    }

    static class MinStack {
        // 数据栈
        private final Stack<Integer> stack = new Stack<>();
        // 辅助栈
        private final Stack<Integer> minStack = new Stack<>();
        /** initialize your data structure here. */
        public MinStack() {

        }

        public void push(int x) {
            stack.add(x);
            if(minStack.isEmpty()){
                minStack.add(x);
            }else {
                if(minStack.peek() <= x){
                    minStack.add(minStack.peek());
                }else{
                    minStack.add(x);
                }
            }
        }

        public void pop() {
            stack.pop();
            minStack.pop();
        }

        public int top() {

            return stack.peek();
        }

        public int min() {
            return minStack.peek();
        }
    }

}
